package middle;

/**
 * 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 *
 * 注意 这个数列必须是 严格 递增的。
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class NumberOfLongestIncreasingSubsequence {
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            int max = 0;
            int ans = 0;
            int[] dp = new int[nums.length];
            int[] count = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                dp[i] = 1;
                count[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[j] < nums[i]) {
                        if (dp[j]+1 > dp[i]) {
                            count[i] = count[j];
                            dp[i] = dp[j] + 1;
                        } else if (dp[j] + 1 == dp[i]) {
                            count[i] += count[j];
                        }
                    }
                }

                if (dp[i] > max) {
                    ans = count[i];
                    max = dp[i];
                } else if (dp[i] == max) {
                    ans += count[i];
                }
            }
            return ans;
        }
    }
}
